/**
 * @file trans.c
 * @author TXG
 * @brief 矩阵转置
 *        假设输入矩阵为A, 输出矩阵为B, 那么有B = A ^ T
 * @version 0.1
 * @date 2021-04-27
 * 
 * @copyright Copyright (c) 2021
 * 
 *  说明:
 *      1.registerFunctions()函数由./test-trans.c文件调用
 *      2.registerTransFunction()函数来自于头文件cachelab.h
 */

/************************************* 宏定义 *************************************/

#define USE_CACHELAB_H

/************************************* 头文件 *************************************/

#include <stdio.h>
#ifdef USE_CACHELAB_H
    #include "cachelab.h"
#endif

/************************************ 全局变量 ************************************/

// registerTransFunction(..., char* desc)函数中的描述字符串参数
char transposeSubmitDesc[] = "Transpose submission";    // 确定的, 不可改

/************************************ 过程函数 ************************************/

/**
 * @brief 实现矩阵的转置 B = A ^ T
 *        根据要求, 矩阵转置函数应有如下格式定义
 *              void trans(int M, int N, int A[N][M], int B[M][N]);
 *        转置函数是通过计算块大小为32字节的1KB直接映射Cache上的未命中数来计算的
 *        针对测试而言考虑3个矩阵的转置: 1)32*32; 2)64*64; 3)61*67      
 * 
 * @param M 矩阵A的行数(矩阵B的列数)
 * @param N 矩阵A的列数(矩阵B的行数)
 * @param A 矩阵A
 * @param B 矩阵B
 */
void transposeSubmit(int M, int N, int A[N][M], int B[M][N]) {
    int blockSize;                      // 块大小
    int blockForRow, blockForCol;       // 矩阵行和列的遍历下标
    int r, c;                           // 划分后行和列的遍历下标
    int temp = 0, d = 0;                // 中间变量, 对角线变量
    int a0, a1, a2, a3, a4, a5, a6, a7; // 64方阵划分使用的变量

    if(N == 32) {
        blockSize = 8;              // 块大小划分为8
        for(blockForCol = 0; blockForCol < N; blockForCol += blockSize) {
            for(blockForRow = 0; blockForRow < M; blockForRow += blockSize) {
                for(r = blockForRow; r < blockForRow + blockSize; ++r) {
                    for(c = blockForCol; c < blockForCol + blockSize; ++c) {
                        if(r != c) {            // 行和列不相等
                            B[c][r] = A[r][c];
                        }
                        else {
                            temp = A[r][c];     // 存储对角线上的值
                            d = r;              // 记录对角线坐标
                        }
                    }
                    if(blockForRow == blockForCol) {
                        B[d][d] = temp;         // 方阵转置对角线不变
                    }
                }
            }
        }
    }
    else if(N == 64) {
        blockSize = 8;              // 块大小划分为8
        int k;
        for(c = 0; c < N; c += blockSize ) {
       	    for(r = 0; r < M; r += blockSize ) {
        	    for(k = 0; k < 4; ++k) { 
                    // 处理A的4 * 8划分
        		    a0 = A[c + k][r + 0];
        		    a1 = A[c + k][r + 1];
        		    a2 = A[c + k][r + 2];
        		    a3 = A[c + k][r + 3];
        		    a4 = A[c + k][r + 4];
        		    a5 = A[c + k][r + 5];
        		    a6 = A[c + k][r + 6];
        		    a7 = A[c + k][r + 7];

        		    B[r + 0][c + k + 0] = a0;   // 转置成功
        		    B[r + 0][c + k + 4] = a5;	// 稍后修改
        		    B[r + 1][c + k + 0] = a1;	// 转置成功
        		    B[r + 1][c + k + 4] = a6;	// 稍后修改
        		    B[r + 2][c + k + 0] = a2;	// 转置成功
        		    B[r + 2][c + k + 4] = a7;	// 稍后修改
        		    B[r + 3][c + k + 0] = a3;	// 转置成功
        		    B[r + 3][c + k + 4] = a4;	// 稍后修改
        	    }

                // 对A的子矩阵进行转置, 并对上一步中的B进行修改
        	    a0 = A[c + 4][r + 4];
        	    a1 = A[c + 5][r + 4];
        	    a2 = A[c + 6][r + 4];
        	    a3 = A[c + 7][r + 4];
        	    a4 = A[c + 4][r + 3];
        	    a5 = A[c + 5][r + 3];
        	    a6 = A[c + 6][r + 3];
        	    a7 = A[c + 7][r + 3];


        	    B[r + 4][c + 0] = B[r + 3][c + 4];  // 例如: B[4][0] = a4 = A[0][4]
        	    B[r + 4][c + 4] = a0;               // 例如: B[4][4] = A[4][4]
        	    B[r + 3][c + 4] = a4;
        	    B[r + 4][c + 1] = B[r + 3][c + 5];
        	    B[r + 4][c + 5] = a1;
        	    B[r + 3][c + 5] = a5;
        	    B[r + 4][c + 2] = B[r + 3][c + 6];
        	    B[r + 4][c + 6] = a2;
        	    B[r + 3][c + 6] = a6;
        	    B[r + 4][c + 3] = B[r + 3][c + 7];
        	    B[r + 4][c + 7] = a3;
        	    B[r + 3][c + 7] = a7;

        	    // 处理剩余的元素
        	    for(k = 0; k < 3; ++k){
        		    a0 = A[c + 4][r + 5 + k];
        		    a1 = A[c + 5][r + 5 + k];
        		    a2 = A[c + 6][r + 5 + k];
        		    a3 = A[c + 7][r + 5 + k];
        		    a4 = A[c + 4][r + k];
        		    a5 = A[c + 5][r + k];
        		    a6 = A[c + 6][r + k];
        		    a7 = A[c + 7][r + k];


        		    B[r + 5 + k][c + 0] = B[r + k][c + 4];
        		    B[r + 5 + k][c + 4] = a0;
        		    B[r + k][c + 4] = a4;
        		    B[r + 5 + k][c + 1] = B[r + k][c + 5];
        		    B[r + 5 + k][c + 5] = a1;
        		    B[r + k][c + 5] = a5;
        		    B[r + 5 + k][c + 2] = B[r + k][c + 6];
        		    B[r + 5 + k][c + 6] = a2;
        		    B[r + k][c + 6] = a6;
        		    B[r + 5 + k][c + 3] = B[r + k][c + 7];
        		    B[r + 5 + k][c + 7] = a3;
        		    B[r + k][c + 7] = a7;
                }
            }
	    }
    }
    else {
        blockSize = 16;              // 块大小划分为16
		for (blockForCol = 0; blockForCol < M; blockForCol += blockSize) {
			for (blockForRow = 0; blockForRow < N; blockForRow += blockSize) {	
				// 矩阵大小可能是奇数, 不是所有的块都是方形的
				for(r = blockForRow; (r < N) && (r < blockForRow + blockSize); ++r) {
					for(c = blockForCol; (c < M) && (c < blockForCol + blockSize); ++c) {
						if (r != c) {
							B[c][r] = A[r][c];
                        }
						else {
							temp = A[r][c];
							d = r;
						}
					}
					
					if(blockForRow == blockForCol) {
						B[d][d] = temp;
					}
				}
			}
		}
    }
}

/**
 * @brief 向驱动器注册编写的矩阵转置函数
 * 
 */
void registerFunctions() {
    #ifdef USE_CACHELAB_H
        registerTransFunction(transposeSubmit, transposeSubmitDesc);
    #endif
    // 当然还可以注册其他的转置函数
}
